The present invention relates generally to data communication networks and more particularly relates to a least recently used (LRU) arbiter based on a linked list mechanism.
Currently, there is a growing trend to make Asynchronous Transfer Mode (ATM) networking technology the base of future global communications. ATM has already been adopted as a standard for broadband communications by the International Telecommunications Union (ITU) and by the ATM Forum, a networking industry consortium.
ATM originated as a telecommunication concept defined by the Comite Consulatif International Telegraphique et Telephonique (CCITT), now known as the ITU, and the American National Standards Institute (ANSI) for carrying user traffic on any User to Network Interface (UNI) and to facilitate multimedia networking between high speed devices at multi-megabit data rates. ATM is a method for transferring network traffic, including voice, video and data, at high speed. Using this connection oriented switched networking technology centered around a switch, a great number of virtual connections can be supported by multiple applications through the same physical connection. The switching technology enables bandwidth to be dedicated for each application, overcoming the problems that exist in a shared media networking technology, like Ethernet, Token Ring and Fiber Distributed Data Interface (FDDI). ATM allows different types of physical layer technology to share the same higher layerxe2x80x94the ATM layer.
More information on ATM networks can be found in the book xe2x80x9cATM: The New Paradigm for Internet, Intranet and Residential Broadband Services and Applications,xe2x80x9d Timothy Kwok, Prentice Hall, 1998.
ATM uses very short, fixed length packets called cells. The first five bytes, called the header, of each cell contain the information necessary to deliver the cell to its destination. The cell header also provides the network with the ability to implement congestion control and traffic management mechanisms. The fixed length cells offer smaller and more predictable switching delays as cell switching is less complex than variable length packet switching and can be accomplished in hardware for many cells in parallel. The cell format also allows for multi-protocol transmissions. Since ATM is protocol transparent, the various protocols can be transported at the same time. With ATM, phone, fax, video, data and other information can be transported simultaneously.
ATM is a connection oriented transport service. To access the ATM network, a station requests a virtual circuit between itself and other end stations, using the signaling protocol to the ATM switch. ATM provides the User Network Interface (UNI) which is typically used to interconnect an ATM user with an ATM switch that is managed as part of the same network.
The environment of the present invention is a data communications network. In a data communications network, data is transferred from end to end, i.e., from source to destination, in data units. Different types of networks give their data units different names. For example, the data units in Ethernet networks are called frames, in ATM networks the data units are called cells and in TCP/IP networks the data units are called packets. A packet (or frame, cell, etc.) is defined as a part of a message that the higher level software application desires to send from a source to a destination or several destinations. In addition, messages can be sent from multiple sources to the same destination.
Each network equipment device has means by which several sources of input data may be destined to the same destination. To manage the flow of data, each destination output has associated with it a queue and some form of control means which functions to manage to flow of data from each of the data sources into the queue. The control means that is utilized in many devices is called an arbiter. It is preferable that the arbiter decide the order in which the data sources load data into the destination queue in a manner that is fair. The decision as to which source should transmit data to the destination queue should preferably also be made as quick as possible in light of (1) the potentially large number of sources vying for the same destination queue and (2) the high data rate of the traffic being carried over the network.
A block diagram illustrating the data flow between multiple sources of data and a destination queue whereby the flow of data to the queue is controlled by an arbiter is shown in FIG. 1. The arbiter portion, generally referenced 10, of the network device comprises a plurality of input data sources labeled input source #1 through input source #N, a plurality of source queues 12 labeled source queue #1 through source queue #N, an arbiter 14, backpressure information source 16 and a destination queue 18.
Each input source transmits data to its corresponding source queue. Each source queue sends both data 20 and an empty flag 22 indicating that the particular source queue is empty. The arbiter receives the data and empty flags from all the source queues and outputs data to the destination queue in accordance with its arbitration scheme. The destination queue transmits data to one or more output ports. The backpressure information source 16 provides backpressure information from downstream processing elements, such as the switching fabric or output ports, to the arbiter.
The explosive growth in networks and the pressing drive for faster data rates is resulting in a larger number of data sources vying to send data to any one destination port. Thus, designers of network equipment are searching for solutions that enable the management of source queues in an intelligent manner such that selection decisions are made at high speed and in a manner fair to the plurality of input data sources. Previous to the recent growth in network use with the high demand for higher speeds and larger bandwidths, the management of input source queues did not create a bottleneck in the flow of network traffic. Thus, a relatively simple and straightforward technique was used.
A description of a prior art implementation of a fair arbitration scheme among several input data sources will now be presented. Diagrams illustrating a prior art source index queue used to determine the order of access to a destination queue by multiple data sources is shown in FIGS. 2A, 2B and 2C. In this type of prior art arbiter implementation, a source index queue 30 is created which includes a plurality of index numbers 32 with each index number corresponding to an input source queue. In addition, the queue includes an indication 34 of the status of each input source queue.
When the arbiter wants to retrieve data from one of the input queues, it cycles through the entries in the source index queue 30, beginning from the top of the queue, searching for the first input source entry that has data, i.e., a packet, available for transmission to the output destination queue. An input source queue that has data ready to transmit has its data ready indication 34 set to a xe2x80x981xe2x80x99. Once a source is selected, its corresponding index number is placed at the end of the source index queue 30 and the other index numbers above it are pushed up one position.
With reference to FIGS. 2A and 2B, it is assumed that there are N sources and one destination. Initially, the order of the contents of the index queue corresponds to the order of the N input source queues, i.e., source #1, #2 . . . #N. An additional bit 34 indicates whether the source has a packet available to transmit to the destination. Note that this bit can be set to xe2x80x980xe2x80x99, i.e., unavailable, due to an empty source queue or due to backpressure from the destination, indicating that this particular source queue is not permitted to send packets.
Now assume, for example, that source #5 is the first source in the index queue with its data ready indication set to a xe2x80x981xe2x80x99. The arbiter searches for the first input source that has a packet of data available for transmission to the destination. In this example source #5 is selected as the source queue to transmit data. Following transmission of the data, the source index #5 is placed at the end of the index queue 30 as represented by arrow 36. Indexes numbered 6 through N are moved up one position.
FIG. 2B shows the state of the index queue after source #5 was read and placed on the bottom of the queue, i.e., given lowest priority. During the next cycle source #3 is the first input source queue with data available to transmit. Note that in FIG. 2A, source #3 had no data available for transmission. This is due to the fact that the available data bit indicators are dynamically updated in response to the input and output ports as described previously and thus they change from cycle to cycle of the arbiter. The data is read from input source queue #3 and then its index is placed at the bottom of the index queue as represented by arrow 40 and shown in FIG. 2C.
Therefore, this prior art arbitration implementation utilizes a least recently used mechanism whereby the queue with data available to send and that has not sent data the longest is the next one to transmit. Note, however, that a growing number of input sources and the increasing data rates of networks create demand for high speed intelligent arbitration solutions. A disadvantage of using the prior art arbitration scheme described above for high speed networks is that the searching process is inefficient in that sources that have no data available to transmit must be checked. In addition, in the worst case, the search process must examine every source queue in the source index queue, thus requiring the examination of N sources. This occurs when only the Nth source queue in the source index queue has data available for transmission.
Another disadvantage is that when shifting the sources up in the index queue, the worst case scenario occurs when all the entries except the first must be shifted up one position. This occurs when the source queue chosen by the arbiter to transmit is the first source queue at the top of the queue. After transmitting, the source index must be placed at the bottom of the index queue, requiring the entire index queue to be shifted up one position. This requires significant amounts of time to be spent on shifting the contents of the source index queue. In addition, additional circuitry, i.e., silicon, is also required to perform the shifting function. As the number of source queues grow, the size of the index queue increases, thus requiring additional time and silicon resources.
The present invention is an arbiter that utilizes a link list to arbitrate access between multiple data sources and a single destination queue. The arbiter is of the least recently used type whereby the data source that has not sent data for the longest time is given the highest priority. This arbitration scheme is a fair method of distributing access to the destination queue among all the data sources.
The arbiter is suitable for applications wherein many input channels want to send data to a single output channel. During each cycle, the arbiter chooses one input channel for data transmission to the output. The LRU mechanism is used to make the arbitration process fair to all input channels. The arbiter of the present invention reduces the arbiter cycle time to a minimum by having the arbiter search only those input channels that have data available to transmit during that cycle.
The arbiter of the present invention provides an arbitration function in a simpler manner and at higher speed than the prior art. The arbiter can be easily implemented in various networking products that handle large numbers of input sources (queues, ports, etc.).
The arbiter creates a linked list of all the input queues that have data available for transmission, i.e., at least one packet of data. Every input queue that was previously empty and now has data to send, is added to the linked list. In addition, every input queue that no longer has any data available for transmission is deleted from the linked list.
The present invention utilizes a linked list method whereby a list is created termed a Non Empty Source Queue (NESQ) list that comprises only sources that are non empty, i.e., that have data ready to send. Using the NESQ list, the average search time to find the next source ready to transmit is now dramatically reduced. The search time is determined by the number of input sources that have data available to send at the time the search is performed.
In addition, after a source queue is chosen for data transmission, the contents of the linked list are reordered to implement the least recently used scheme by updating two pointers. No shifting of any of the sources on the list is required as was the case with the prior art arbiter scheme. When a source queue becomes empty after the transmission of data, the source index is removed from the linked list. Conversely, when a source queue that was previously empty, i.e., is not on the linked list, receives a new packet, it will be added to the end of the linked list.
The arbiter of the present invention performs two main methods in implementing the arbitration function: (1) adding a new input source queue to the liked list and (2) searching for a source queue with data ready to transmit and subsequently removing them from the linked list.
There is provided in accordance with the present invention an arbiter for managing data flow between a plurality of input sources and an output destination comprising a non empty source queue (NESQ) having a plurality of entries, each entry corresponding to one input source and comprising a data pointer, a linked list containing an ordered list of pointers to input sources, the ordered list having a head and a tail pointed to by a head pointer and a tail pointer, respectively, the ordered list representing the order the plurality of input sources are permitted to send data to the output destination, wherein input sources are selected from the head of the linked list, once a selected source transmits data, it is placed at the tail of the linked list if it has additional data to transmit and is removed from the linked list otherwise and wherein an input source not previously on the linked list is added thereto when the input source has data available for transmission.
The NESQ list comprises a block of memory and a backpressure indication associated with each input source wherein an input source is not permitted to transmit data to the output destination if its associated backpressure indication is positive.
An input source is added to the NESQ list by writing the source index of the input source to be added to the entry in the NESQ list pointed to by the tail pointer followed by setting the tail pointer to the input source to be added. Input sources are selected from the NESQ list by scanning beginning with the entry pointed to be the head pointer and continuing with the entry pointed to by the data pointer associated therewith.
There is also provided in accordance with the present invention an arbiter for managing data flow between a plurality of input sources and an output destination comprising a non empty source queue (NESQ) having a plurality of entries, each entry corresponding to one input source and comprising a data pointer, a linked list containing an ordered list of pointers to input sources, the ordered list having a head and a tail pointed to by a head pointer and a tail pointer, respectively, the ordered list representing the order the plurality of input sources are permitted to send data to the output destination, means for adding an input source to the NESQ list when the input source has data available for transmission, means for selecting an input source from among those input sources ready to transmit data, means for transmitting data from the selected input source and subsequently removing the selected input source from the linked list and means for placing the selected input source at the tail of the linked list if the selected input source has additional data to transmit.